#include<iostream>
using namespace std;
#include<string>
#include<vector>

int MinofThree(int a, int b, int c)
{
	int min = a;
	if (b < min)
		min = b;
	if (c < min)
		min = c;
	return min;
}


int GetLevDis(string s1, string s2)
{
	int m = s1.length();
	int n = s2.length();
	vector<vector<int>> vv(m+1,vector<int>(n+1,0));
	vv[0][0] = 0;
	for (int i = 1; i <= m; ++i)
	{
		vv[i][0] = i;
		for (int j = 1; j <= n; ++j)
		{
			vv[0][j] = j;
			int emo = 0;
			if (s1[i - 1] != s2[j - 1])
				emo = 1;
			vv[i][j] = MinofThree(vv[i - 1][j] + 1, vv[i][j - 1] + 1, vv[i - 1][j - 1] + emo);
		}
	}
	return vv[m][n];
}

int main()
{
	string s1, s2;
	while (cin >> s1 >> s2)
	{
		int ret = GetLevDis(s1, s2);
		cout << ret << endl;
	}
	return 0;
}